\documentclass[12pt]{report}
\usepackage{geometry}
\geometry{a4paper,scale=0.8}
\usepackage{longtable}
\usepackage{url}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{float}
\usepackage{titlesec}
\usepackage{CJK}
\begin{CJK}{UTF8}{gkai}
%\titleformat{\chapter}[hang]{\centering\Huge\bfseries}{\chaptername}{1em}{}
%\renewcommand{\chaptername}{第\CJKnumber{thechapter}章}
\title{A003 学习linux0.01内核调度}
\author{Chuzy}
\date{2020/05/03}

\lstset{
    basicstyle          =   \small\ttfamily,          % 基本代码风格
    keywordstyle        =   \bfseries,          % 关键字风格
    commentstyle        =   \rmfamily\itshape,  % 注释的风格，斜体
    stringstyle         =   \ttfamily,  % 字符串风格
    flexiblecolumns,                % 别问为什么，加上这个
    numbers             =   left,   % 行号的位置在左边
    showspaces          =   false,  % 是否显示空格，显示了有点乱，所以不现实了
    numberstyle         =   \ttfamily,    % 行号的样式，小五号，tt等宽字体
    showstringspaces    =   false,
    captionpos          =   t,      % 这段代码的名字所呈现的位置，t指的是top上面
    frame               =   lrtb,   % 显示边框
    columns         =   flexible,     
    breaklines      =   true,
    language        =  [ANSI]C,
    escapeinside=``
}


%以上部分叫做"导言区",下面才开始写正文
\begin{document}

%先插入标题
\maketitle
\tableofcontents
\newpage 
\chapter{概述}
在002中我们给内核增加打印功能，并了解了console的初始化；在003版本，我们将创建两个新的任务，观察这两个任务的调度运行情况，并为此增加分页内存管理机制。
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.5]{fig/35.png}
\caption{003版本运行结果}
\label{fig:Version 003}
\end{figure}
\chapter{流程图}
为了保持清晰，相对0.002版本没有变化的文件，将不在列出。
\begin{longtable}{|l|l|p{5cm}|p{3cm}|} 
\caption{0.003版本的文件}  
\label{tab: 0.003 files} \\ 
\hline 目录 & 文件名 & 描述 & 相对上一版本\\
\hline / & Makefile & 增加新目录 & 变化\\ 
\hline  /init & main.c & 创建新任务 & 变化\\
\hline  /kernel & panic.c & 内核异常处理 & 新增 \\
\hline  /kernel & exit.c & 任务退出时清理 & 新增 \\
\hline  /kernel & traps.c & 设置中断处理 & 新增 \\
\hline  /kernel & sched.c & 调度 & 变化\\
\hline  /kernel & asm.s & 错误处理的汇编代码 & 新增 \\
\hline  /kernel & system\_call.s & 系统调用 & 新增 \\
\hline  /kernel & Makefile & 增加了新文件 & 变化\\
\hline  /lib & \_exit.c & 直接通过系统调用退出 & 新增 \\
\hline  /lib & errno.c & 定义错误码 & 新增 \\
\hline  /lib & ctype.c & 定义字符类型 & 新增 \\
\hline  /lib & Makefile & lib目录的Makefile & 新增 \\
\hline  /include & config.h & 系统配置 & 增加 \\
\hline  /include & ctype.h & 字符类型 & 增加 \\
\hline  /include & errno.h & 错误吗 & 增加 \\
\hline  /include & signal.h & 进程控制信号 & 增加 \\
\hline  /include & time.h & 终端输入输出 & 增加 \\
\hline  /include & unistd.h & 标准系统调用 & 增加 \\
\hline  /include/linux & fs.h & 文件管理系统 & 新增 \\
\hline  /include/linux & head.h & head.s中定义的关键结构 & 新增 \\
\hline  /include/linux & kernel.h & 内核函数原型 & 新增 \\
\hline  /include/linux & sched.h & 调度数据结构 & 新增 \\
\hline  /include/linux & sys.h & 系统调用表 & 新增 \\
\hline  
\end{longtable}  
\paragraph{} 我们首先在main函数中增加了trap和调度器sched的初始化。随后，我们在main函数通过fork创建一个进程(进程1)，在这个进程中调用init函数，在其中再创建一个进程(进程2)；然后，我们在定时器中断处理函数中增加两个进程的CPU占用时间统计（每5s输出一次）。
\paragraph{进程和进程内存} 在head.s中，我们设置了一个有1024个页面的页目录，每页面又有1024个页面项，每个页面项对应4K物理内存，总共可寻址1024 * 1024 * 4k = 4GB的内存空间。我们支持64个进程，因此每个进程就可以分得4GB / 64 = 64MB的独立内存空间。 
\paragraph{定时器和调度} 在多进程系统中，调度器依赖8253可编程计数器计数器/定时器芯片产生的中断来打断进程的执行，并根据每个进程的优先级和已经执行的时间，来确定下一个时刻应该由那个进程来执行。

\chapter{初始化流程控制源码init/main.c}
\section{main函数}
在main函数中，完成各种初始化之后，当前运行的程序进入用户态，成为进程0；进程0创建了1个新的进程之后进入循环pause, 新创建的进程，即进程1, 进入自己的处理，调用init继续完成初始化过程。
\begin{lstlisting}[breaklines]
#define __LIBRARY__
#include <unistd.h>

/*
 * we need this inline - forking from kernel space will result
 * in NO COPY ON WRITE (!!!), until an execve is executed. This
 * is no problem, but for the stack. This is handled by not letting
 * main() use the stack at all after fork(). Thus, no function
 * calls - which means inline code for fork too, as otherwise we
 * would use the stack upon exit from 'fork()'.
 *
 * Actually only pause and fork are needed inline, so that there
 * won't be any messing with the stack from main(), but we define
 * some others too.
 */
inline _syscall0(int,fork)	/* `系统调用，用户态通过int80调用sys\_fork` */
inline _syscall0(int,pause)	/* `系统调用，用户态通过int80调用sys\_pause` */
#include <time.h>

#include <linux/tty.h>
#include <linux/sched.h>
#include <linux/head.h>
#include <asm/system.h>
#include <asm/io.h>

#include <stddef.h>
#include <stdarg.h>
#include <unistd.h>
//#include <fcntl.h>
#include <sys/types.h>

#include <linux/fs.h>

static char printbuf[1024];

extern int vsprintf();
//extern void init(void);
//extern void hd_init(void);
extern long kernel_mktime(struct tm * tm);
extern long startup_time;
extern int printk(const char *fmt, ...);

#define CMOS_READ(addr) ({ \
outb_p(0x80|addr,0x70); \
inb_p(0x71); \
})

#define BCD_TO_BIN(val) ((val)=((val)&15) + ((val)>>4)*10)

static void time_init(void)
{
        struct tm time;

        do {
                time.tm_sec = CMOS_READ(0);
                time.tm_min = CMOS_READ(2);
                time.tm_hour = CMOS_READ(4);
                time.tm_mday = CMOS_READ(7);
                time.tm_mon = CMOS_READ(8)-1;
                time.tm_year = CMOS_READ(9);
        } while (time.tm_sec != CMOS_READ(0));
        BCD_TO_BIN(time.tm_sec);
        BCD_TO_BIN(time.tm_min);
        BCD_TO_BIN(time.tm_hour);
        BCD_TO_BIN(time.tm_mday);
        BCD_TO_BIN(time.tm_mon);
        BCD_TO_BIN(time.tm_year);
        startup_time = kernel_mktime(&time);
}


int main(void)
{

    time_init();
    tty_init();
    trap_init();
    sched_init();
    sti();
    move_to_user_mode();
    if (!fork()) {	/* `通过fork创建新的进程，返回0说明在新进程task[1]中` */		 
        init();
    }

    for(;;) pause();	/* task[0], `idle进程` */		
    return 0;
}

static char * argv[] = { "-",NULL };
static char * envp[] = { "HOME=/usr/root", NULL };
\end{lstlisting}
\section{init函数}
进程1在init函数中创建了进程2, 自己进入无限循环；而进程2创建出来之后，也进入无限循环。这样，我们就有1/2两个进程始终处于运行状态。
\begin{lstlisting}[breaklines]
void init(void)
{
    if (!fork())	/* `通过fork创建新的进程，返回0说明是在新的进程中` */	
        for(;;);	/* task[2], `死循环` */
    for(;;);		/* task[1], `死循环` */
}
\end{lstlisting}
\chapter{内核异常处理源码kernel/asm.s}
处理底层的硬件错误，我们一般用不到。
\begin{lstlisting}[breaklines]
/*
 * asm.s contains the low-level code for most hardware faults.
 * page_exception is handled by the mm, so that isn't here. This
 * file also handles (hopefully) fpu-exceptions due to TS-bit, as
 * the fpu must be properly saved/resored. This hasn't been tested.
 */

.globl divide_error,debug,nmi,int3,overflow,bounds,invalid_op
.globl device_not_available,double_fault,coprocessor_segment_overrun
.globl invalid_TSS,segment_not_present,stack_segment
.globl general_protection,coprocessor_error,reserved

divide_error:
	pushl $do_divide_error
no_error_code:
	xchgl %eax,(%esp)
	pushl %ebx
	pushl %ecx
	pushl %edx
	pushl %edi
	pushl %esi
	pushl %ebp
	push %ds
	push %es
	push %fs
	pushl $0		# "error code"
	lea 44(%esp),%edx
	pushl %edx
	movl $0x10,%edx
	mov %dx,%ds
	mov %dx,%es
	mov %dx,%fs
	call *%eax
	addl $8,%esp
	pop %fs
	pop %es
	pop %ds
	popl %ebp
	popl %esi
	popl %edi
	popl %edx
	popl %ecx
	popl %ebx
	popl %eax
	iret

debug:
	pushl $do_int3		# _do_debug
	jmp no_error_code

nmi:
	pushl $do_nmi
	jmp no_error_code

int3:
	pushl $do_int3
	jmp no_error_code

overflow:
	pushl $do_overflow
	jmp no_error_code

bounds:
	pushl $do_bounds
	jmp no_error_code

invalid_op:
	pushl $do_invalid_op
	jmp no_error_code

math_emulate:
	popl %eax
	pushl $do_device_not_available
	jmp no_error_code
device_not_available:
	pushl %eax
	movl %cr0,%eax
	bt $2,%eax			# EM (math emulation bit)
	jc math_emulate
	clts				# clear TS so that we can use math
	movl current,%eax
	cmpl last_task_used_math,%eax
	je 1f				# shouldn't happen really ...
	pushl %ecx
	pushl %edx
	push %ds
	movl $0x10,%eax
	mov %ax,%ds
	call math_state_restore
	pop %ds
	popl %edx
	popl %ecx
1:	popl %eax
	iret

coprocessor_segment_overrun:
	pushl $do_coprocessor_segment_overrun
	jmp no_error_code

reserved:
	pushl $do_reserved
	jmp no_error_code

coprocessor_error:
	pushl $do_coprocessor_error
	jmp no_error_code

double_fault:
	pushl $do_double_fault
error_code:
	xchgl %eax,4(%esp)		# error code <-> %eax
	xchgl %ebx,(%esp)		# &function <-> %ebx
	pushl %ecx
	pushl %edx
	pushl %edi
	pushl %esi
	pushl %ebp
	push %ds
	push %es
	push %fs
	pushl %eax			# error code
	lea 44(%esp),%eax		# offset
	pushl %eax
	movl $0x10,%eax
	mov %ax,%ds
	mov %ax,%es
	mov %ax,%fs
	call *%ebx
	addl $8,%esp
	pop %fs
	pop %es
	pop %ds
	popl %ebp
	popl %esi
	popl %edi
	popl %edx
	popl %ecx
	popl %ebx
	popl %eax
	iret

invalid_TSS:
	pushl $do_invalid_TSS
	jmp error_code

segment_not_present:
	pushl $do_segment_not_present
	jmp error_code

stack_segment:
	pushl $do_stack_segment
	jmp error_code

general_protection:
	pushl $do_general_protection
	jmp error_code
\end{lstlisting}

\chapter{进程退出处理源码kernel/exit.c}
进程退出时的处理，我们现在还用不到。
\begin{lstlisting}[breaklines]

#include <errno.h>
#include <signal.h>
#include <sys/wait.h>

#include <linux/sched.h>
#include <linux/kernel.h>
#include <linux/tty.h>
#include <asm/segment.h>

int sys_pause(void);
//int sys_close(int fd);

void release(struct task_struct * p)
{
	int i;

	if (!p)
		return;
	for (i=1 ; i<NR_TASKS ; i++)
		if (task[i]==p) {
			task[i]=NULL;
			free_page((long)p);
			schedule();
			return;
		}
	panic("trying to release non-existent task");
}

static inline void send_sig(long sig,struct task_struct * p,int priv)
{
	if (!p || sig<1 || sig>32)
		return;
	if (priv ||
		current->uid==p->uid ||
		current->euid==p->uid ||
		current->uid==p->euid ||
		current->euid==p->euid)
		p->signal |= (1<<(sig-1));
}

void do_kill(long pid,long sig,int priv)
{
	struct task_struct **p = NR_TASKS + task;

	if (!pid) while (--p > &FIRST_TASK) {
		if (*p && (*p)->pgrp == current->pid)
			send_sig(sig,*p,priv);
	} else if (pid>0) while (--p > &FIRST_TASK) {
		if (*p && (*p)->pid == pid)
			send_sig(sig,*p,priv);
	} else if (pid == -1) while (--p > &FIRST_TASK)
		send_sig(sig,*p,priv);
	else while (--p > &FIRST_TASK)
		if (*p && (*p)->pgrp == -pid)
			send_sig(sig,*p,priv);
}

int sys_kill(int pid,int sig)
{
	do_kill(pid,sig,!(current->uid || current->euid));
	return 0;
}

int do_exit(long code)
{
	int i;

	free_page_tables(get_base(current->ldt[1]),get_limit(0x0f));
	free_page_tables(get_base(current->ldt[2]),get_limit(0x17));
	for (i=0 ; i<NR_TASKS ; i++)
		if (task[i] && task[i]->father == current->pid)
			task[i]->father = 0;
//	for (i=0 ; i<NR_OPEN ; i++)
//		if (current->filp[i])
//			sys_close(i);
//	iput(current->pwd);
	current->pwd=NULL;
//	iput(current->root);
	current->root=NULL;
	if (current->leader && current->tty >= 0)
		tty_table[current->tty].pgrp = 0;
	if (last_task_used_math == current)
		last_task_used_math = NULL;
	if (current->father) {
		current->state = TASK_ZOMBIE;
		do_kill(current->father,SIGCHLD,1);
		current->exit_code = code;
	} else
		release(current);
	schedule();
	return (-1);	/* just to suppress warnings */
}

int sys_exit(int error_code)
{
	return do_exit((error_code&0xff)<<8);
}

int sys_waitpid(pid_t pid,int * stat_addr, int options)
{
	int flag=0;
	struct task_struct ** p;

	verify_area(stat_addr,4);
repeat:
	for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
		if (*p && *p != current &&
		   (pid==-1 || (*p)->pid==pid ||
		   (pid==0 && (*p)->pgrp==current->pgrp) ||
		   (pid<0 && (*p)->pgrp==-pid)))
			if ((*p)->father == current->pid) {
				flag=1;
				if ((*p)->state==TASK_ZOMBIE) {
					put_fs_long((*p)->exit_code,
						(unsigned long *) stat_addr);
					current->cutime += (*p)->utime;
					current->cstime += (*p)->stime;
					flag = (*p)->pid;
					release(*p);
					return flag;
				}
			}
	if (flag) {
		if (options & WNOHANG)
			return 0;
		sys_pause();
		if (!(current->signal &= ~(1<<(SIGCHLD-1))))
			goto repeat;
		else
			return -EINTR;
	}
	return -ECHILD;
}
\end{lstlisting}
\chapter{进程创建源码kernel/fork.c}
整个内核就是围绕着进程和调度来进行的，在fork.c中实现了进程的创建，为进程分配内存空间，并根据父进程的内容初始化新的进程。
\begin{lstlisting}[breaklines]
/*
 *  'fork.c' contains the help-routines for the 'fork' system call
 * (see also system_call.s), and some misc functions ('verify_area').
 * Fork is rather simple, once you get the hang of it, but the memory
 * management can be a bitch. See 'mm/mm.c': 'copy_page_tables()'
 */
#include <errno.h>

#include <linux/sched.h>
#include <linux/kernel.h>
#include <asm/segment.h>
#include <asm/system.h>

extern void write_verify(unsigned long address);

long last_pid=0;
\end{lstlisting}
\section{verify\_area函数}
80386的CPU，特权级为0的内核代码不会理会用户空间的页面是有页保护的，因此需要通过检查页面是否可写触发copy-on-write。而这种检查是以页为单位的，因此，首先将addr和size转换到4k对齐。
\paragraph{写时复制} copy-on-write，在fork之后exec之前父子两个进程用的是相同的物理空间（内存区），子进程的代码段、数据段、堆栈都是指向父进程的物理空间，也就是说，两者的虚拟空间不同，但其对应的物理空间是同一个。当父子进程中有更改相应段的行为（通常是exec）发生时，再为子进程相应的段分配物理空间。
\begin{lstlisting}[breaklines]
void verify_area(void * addr,int size)
{
	unsigned long start;

	start = (unsigned long) addr;
	size += start & 0xfff;	/*`假如addr未4k对齐，把start前移，对应size增加`*/
	start &= 0xfffff000;	/*`4k取整，start前移`*/
	start += get_base(current->ldt[2]);	/*`ldt[2]即数据段`*/
	while (size>0) {	
		size -= 4096;
		write_verify(start);	/*`写页面验证，若不可写，复制页面`*/
		start += 4096;
	}
}
\end{lstlisting}
\section{copy\_mem函数}
在LDT中只有code和data两个段，我们现在只支持这两个段基地址相同，段长相同，因此只用复制一份。
\paragraph{进程内存空间} 在head.s中，我们设置了一个有1024个页面的页目录，每页面又有1024个页面项，每个页面项对应4K物理内存，总共可寻址1024 * 1024 * 4k = 4GB的内存空间。我们支持64个进程，因此每个进程就可以分得4GB / 64 = 64MB的独立内存空间。而在copy\_page\_tables 中要做的则是4GB的分页内存空间到8MB的物理内存的映射。
\begin{lstlisting}[breaklines]
int copy_mem(int nr,struct task_struct * p)
{
	unsigned long old_data_base,new_data_base,data_limit;
	unsigned long old_code_base,new_code_base,code_limit;

	code_limit=get_limit(0x0f);
	data_limit=get_limit(0x17);
	old_code_base = get_base(current->ldt[1]);
	old_data_base = get_base(current->ldt[2]);
	if (old_data_base != old_code_base)
		panic("We don't support separate I&D");
	if (data_limit < code_limit)
		panic("Bad data_limit");
	new_code_base = nr * 0x4000000;	/*nr * 64MB*/
	new_data_base = new_code_base;
	set_base(p->ldt[1],new_code_base);
	set_base(p->ldt[2],new_data_base);
	if (copy_page_tables(old_data_base,new_data_base,data_limit)) {
		free_page_tables(new_data_base,data_limit);
		return -ENOMEM;
	}
	return 0;
}
\end{lstlisting}
\section{copy\_process函数}
进程有两部分内存，一部分是在内核中，由task[]指向的内存，一个进程占用一个页面（4k），页面的头部是一个task\_struct 结构，页面从后往前则是内核态堆栈；另一部分内存则是进程LDT指向的进程的代码段和数据段空间。
\paragraph{bug?} 下面代码中的cld指令是我后加的，原代码中没有，实际仿真时发现若无此语句，*p = *current会按照相反的方向赋值。
\begin{lstlisting}[breaklines]
/*
 *  Ok, this is the main fork-routine. It copies the system process
 * information (task[nr]) and sets up the necessary registers. It
 * also copies the data segment in it's entirety.
 */
int copy_process(int nr,long ebp,long edi,long esi,long gs,long none,
		long ebx,long ecx,long edx,
		long fs,long es,long ds,
		long eip,long cs,long eflags,long esp,long ss)
{
	struct task_struct *p;
	int i;
	struct file *f;

	p = (struct task_struct *) get_free_page();
	if (!p)
		return -EAGAIN;
	__asm__ ("cld"::);
	*p = *current;	/* `复制task\_struct的全部内容` */
	p->state = TASK_RUNNING;
	p->pid = last_pid;
	p->father = current->pid;
	p->counter = p->priority;
	p->signal = 0;
	p->alarm = 0;
	p->leader = 0;		/* process leadership doesn't inherit */
	p->utime = p->stime = 0;
	p->cutime = p->cstime = 0;
	p->start_time = jiffies;
	p->tss.back_link = 0;
	p->tss.esp0 = PAGE_SIZE + (long) p;	/* `内核态栈顶` */
	p->tss.ss0 = 0x10;
	p->tss.eip = eip;
	p->tss.eflags = eflags;
	p->tss.eax = 0;		/* `子进程fork返回值为0` */
	p->tss.ecx = ecx;
	p->tss.edx = edx;
	p->tss.ebx = ebx;
	p->tss.esp = esp;
	p->tss.ebp = ebp;
	p->tss.esi = esi;
	p->tss.edi = edi;
	p->tss.es = es & 0xffff;
	p->tss.cs = cs & 0xffff;
	p->tss.ss = ss & 0xffff;
	p->tss.ds = ds & 0xffff;
	p->tss.fs = fs & 0xffff;
	p->tss.gs = gs & 0xffff;
	p->tss.ldt = _LDT(nr);
	p->tss.trace_bitmap = 0x80000000;
	if (last_task_used_math == current)
		__asm__("fnsave %0"::"m" (p->tss.i387));
	if (copy_mem(nr,p)) {		/* `复制LDT指向的代码段和数据段` */
		free_page((long) p);
		return -EAGAIN;
	}
	for (i=0; i<NR_OPEN;i++)
		if (f=p->filp[i])
			f->f_count++;
	if (current->pwd)
		current->pwd->i_count++;
	if (current->root)
		current->root->i_count++;
	set_tss_desc(gdt+(nr<<1)+FIRST_TSS_ENTRY,&(p->tss));
	set_ldt_desc(gdt+(nr<<1)+FIRST_LDT_ENTRY,&(p->ldt));
	task[nr] = p;	/* do this last, just in case */
	return last_pid;
}
\end{lstlisting}
\section{find\_empty\_process函数}
为进程找到一个不重复的pid，以及一个空闲的task数组索引。
\begin{lstlisting}[breaklines]
int find_empty_process(void)
{
	int i;

	repeat:
		if ((++last_pid)<0) last_pid=1;
		for(i=0 ; i<NR_TASKS ; i++)	/* `pid不能重复` */
			if (task[i] && task[i]->pid == last_pid) goto repeat;
	for(i=1 ; i<NR_TASKS ; i++)
		if (!task[i])
			return i;
	return -EAGAIN;
}
\end{lstlisting}
\chapter{时间转换源码kernel/mktime.c}
我们暂时还用不到。
\begin{lstlisting}[breaklines]
#include <time.h>
/*
 * This isn't the library routine, it is only used in the kernel.
 * as such, we don't care about years<1970 etc, but assume everything
 * is ok. Similarly, TZ etc is happily ignored. We just do everything
 * as easily as possible. Let's find something public for the library
 * routines (although I think minix times is public).
 */
/*
 * PS. I hate whoever though up the year 1970 - couldn't they have gotten
 * a leap-year instead? I also hate Gregorius, pope or no. I'm grumpy.
 */
#define MINUTE 60
#define HOUR (60*MINUTE)
#define DAY (24*HOUR)
#define YEAR (365*DAY)

/* interestingly, we assume leap-years */
static int month[12] = {
        0,
        DAY*(31),
        DAY*(31+29),
        DAY*(31+29+31),
        DAY*(31+29+31+30),
        DAY*(31+29+31+30+31),
        DAY*(31+29+31+30+31+30),
        DAY*(31+29+31+30+31+30+31),
        DAY*(31+29+31+30+31+30+31+31),           
        DAY*(31+29+31+30+31+30+31+31+30),
        DAY*(31+29+31+30+31+30+31+31+30+31),
        DAY*(31+29+31+30+31+30+31+31+30+31+30)
};

long kernel_mktime(struct tm * tm)
{
        long res;
        int year;

        year = tm->tm_year - 70;
/* magic offsets (y+1) needed to get leapyears right.*/
        res = YEAR*year + DAY*((year+1)/4);
        res += month[tm->tm_mon];
/* and (y+2) here. If it wasn't a leap-year, we have to adjust */
        if (tm->tm_mon>1 && ((year+2)%4))
                res -= DAY;
        res += DAY*(tm->tm_mday-1);
        res += HOUR*tm->tm_hour;
        res += MINUTE*tm->tm_min;
        res += tm->tm_sec;
        return res;
}
\end{lstlisting}
\chapter{内核异常终止源码kernel/panic.c}
打印内核异常，并进入无限循环。
\begin{lstlisting}[breaklines]
/*
 * This function is used through-out the kernel (includeinh mm and fs)
 * to indicate a major problem.
 */
#include <linux/kernel.h>

volatile void panic(const char * s)
{
	printk("Kernel panic: %s\n\r",s);
	for(;;);
}
\end{lstlisting}
\chapter{内核调度源码kernel/sched.c}
\begin{lstlisting}[breaklines]
/*
 * 'sched.c' is the main kernel file. It contains scheduling primitives
 * (sleep_on, wakeup, schedule etc) as well as a number of simple system
 * call functions (type getpid(), which just extracts a field from
 * current-task
 */
#include <linux/sched.h>
#include <linux/kernel.h>
#include <signal.h>
#include <linux/sys.h>
#include <asm/system.h>
#include <asm/io.h>
#include <asm/segment.h>

#define LATCH (1193180/HZ)

extern void mem_use(void);

extern int timer_interrupt(void);
extern int system_call(void);

union task_union {
	struct task_struct task;
	char stack[PAGE_SIZE];
};

static union task_union init_task = {INIT_TASK,};

long volatile jiffies=0;
long startup_time=0;
struct task_struct *current = &(init_task.task), *last_task_used_math = NULL;

struct task_struct * task[NR_TASKS] = {&(init_task.task), };

long user_stack [ PAGE_SIZE>>2 ] ;

struct {
	long * a;
	short b;
	} stack_start = { & user_stack [PAGE_SIZE>>2] , 0x10 };
/*
 *  'math_state_restore()' saves the current math information in the
 * old math state array, and gets the new ones from the current task
 */
void math_state_restore()
{
	if (last_task_used_math)
		__asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
	if (current->used_math)
		__asm__("frstor %0"::"m" (current->tss.i387));
	else {
		__asm__("fninit"::);
		current->used_math=1;
	}
	last_task_used_math=current;
}
\end{lstlisting}

\section{schedule函数}
schedule函数要么由定时器触发，要么由进入等待状态的进程触发。首先遍历所有处于pause状态的任务，如果任务收到信号，则将任务置为运行状态，以处理对应的信号; 然后进入循环，找到counter最大的处于运行态的任务，切换到该任务; 如果没有找到任何运行态的任务，则循环更新所有任务的counter;
\begin{lstlisting}[breaklines]
/*
 *  'schedule()' is the scheduler function. This is GOOD CODE! There
 * probably won't be any reason to change this, as it should work well
 * in all circumstances (ie gives IO-bound processes good response etc).
 * The one thing you might take a look at is the signal-handler code here.
 *
 *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
 * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 * information in task[0] is never used.
 */
void schedule(void)
{
	int i,next,c;
	struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */

	for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
		if (*p) {
			if ((*p)->alarm && (*p)->alarm < jiffies) {
					(*p)->signal |= (1<<(SIGALRM-1));
					(*p)->alarm = 0;
				}
			if ((*p)->signal && (*p)->state==TASK_INTERRUPTIBLE)
				(*p)->state=TASK_RUNNING;
		}

/* this is the scheduler proper: */

	while (1) {
		c = -1;
		next = 0;
		i = NR_TASKS;
		p = &task[NR_TASKS];
		while (--i) {
			if (!*--p)
				continue;
			if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
				c = (*p)->counter, next = i;
		}
		if (c) break;
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			if (*p)
				(*p)->counter = ((*p)->counter >> 1) +
						(*p)->priority;
	}
	switch_to(next);
}
\end{lstlisting}
\section{sys\_pause函数}
在调用pause函数时，实际上产生了一个指向sys\_pause的系统调用, 将当前任务状态置为TASK\_INTERRUPTIBLE， 然后主动触发schedule函数;
\begin{lstlisting}[breaklines]
int sys_pause(void)
{
	current->state = TASK_INTERRUPTIBLE;
	schedule();
	return 0;
}

void sleep_on(struct task_struct **p)
{
	struct task_struct *tmp;

	if (!p)
		return;
	if (current == &(init_task.task))
		panic("task[0] trying to sleep");
	tmp = *p;
	*p = current;
	current->state = TASK_UNINTERRUPTIBLE;
	schedule();
	if (tmp)
		tmp->state=0;
}

void interruptible_sleep_on(struct task_struct **p)
{
	struct task_struct *tmp;

	if (!p)
		return;
	if (current == &(init_task.task))
		panic("task[0] trying to sleep");
	tmp=*p;
	*p=current;
repeat:	current->state = TASK_INTERRUPTIBLE;
	schedule();
	if (*p && *p != current) {
		(**p).state=0;
		goto repeat;
	}
	*p=NULL;
	if (tmp)
		tmp->state=0;
}

void wake_up(struct task_struct **p)
{
	if (p && *p) {
		(**p).state=0;
		*p=NULL;
	}
}
\end{lstlisting}
\section{do\_timer函数}
被中断处理函数为timer\_interrupt调用，根据当前任务的CPL，统计utime或者是stime，然后返回到调度器处理; 我们在这里增加一个内核打印语句，用于判断定时器和调度任务是否正常;
\begin{lstlisting}[breaklines]
void do_timer(long cpl)
{
	if (cpl){
		current->utime++;
		if((current->utime % 500) == 0)
		    printk("pid: 0x%x, utime:0x%x\n", current->pid, current->utime);
        }
	else
		current->stime++;
	if ((--current->counter)>0) return;
	current->counter=0;
	if (!cpl) return;
	schedule();
}

int sys_alarm(long seconds)
{
	current->alarm = (seconds>0)?(jiffies+HZ*seconds):0;
	return seconds;
}

int sys_getpid(void)
{
	return current->pid;
}

int sys_getppid(void)
{
	return current->father;
}

int sys_getuid(void)
{
	return current->uid;
}

int sys_geteuid(void)
{
	return current->euid;
}

int sys_getgid(void)
{
	return current->gid;
}

int sys_getegid(void)
{
	return current->egid;
}

int sys_nice(long increment)
{
	if (current->priority-increment>0)
		current->priority -= increment;
	return 0;
}

int sys_signal(long signal,long addr,long restorer)
{
	long i;

	switch (signal) {
		case SIGHUP: case SIGINT: case SIGQUIT: case SIGILL:
		case SIGTRAP: case SIGABRT: case SIGFPE: case SIGUSR1:
		case SIGSEGV: case SIGUSR2: case SIGPIPE: case SIGALRM:
		case SIGCHLD:
			i=(long) current->sig_fn[signal-1];
			current->sig_fn[signal-1] = (fn_ptr) addr;
			current->sig_restorer = (fn_ptr) restorer;
			return i;
		default: return -1;
	}
}
\end{lstlisting}
\section{sched\_init函数}
linux最多支持NR\_TASKS个任务，在定时器中断的驱动下，由调度器对这些任务进行调度。init\_task是系统中第一个任务，后续所有任务都将从init\_task中创建。
\begin{lstlisting}[breaklines]
void sched_init(void)
{
	int i;
	struct desc_struct * p;

	set_tss_desc(gdt+FIRST_TSS_ENTRY,&(init_task.task.tss));
	set_ldt_desc(gdt+FIRST_LDT_ENTRY,&(init_task.task.ldt));
	p = gdt+2+FIRST_TSS_ENTRY;
	for(i=1;i<NR_TASKS;i++) {
		task[i] = NULL;
		p->a=p->b=0;
		p++;
		p->a=p->b=0;
		p++;
	}
	ltr(0);	/* `ltr和lldt是封装之后的函数，将参数转换为GDT中对应的选择符` */
	lldt(0);
	outb_p(0x36,0x43);		/* binary, mode 3, LSB/MSB, ch 0 */
	outb_p(LATCH & 0xff , 0x40);	/* LSB */
	outb(LATCH >> 8 , 0x40);	/* MSB */
	set_intr_gate(0x20,&timer_interrupt);
	outb(inb_p(0x21)&~0x01,0x21);	/* `允许时钟中断` */
	set_system_gate(0x80,&system_call);
}
\end{lstlisting}
\chapter{内核系统调用源码kernel/system\_call.s}
在linux0.01中，用户使用中断调用int 80h和存放在寄存器eax中的功能号来使用内核提供的各种功能服务，这些操作系统提供的功能被成为系统调用功能。对于所有系统调用的实现函数，按照系统调用功能号的顺序排成一张函数指针表sys\_call\_table （include/linux/sys.h）。int 80h对应的处理函数为system\_call， 该函数检查输入的eax值，并根据eax值调用sys\_call\_table 对应的处理函数。
\begin{lstlisting}[breaklines]
/*
 *  system_call.s  contains the system-call low-level handling routines.
 * This also contains the timer-interrupt handler, as some of the code is
 * the same. The hd-interrupt is also here.
 *
 * NOTE: This code handles signal-recognition, which happens every time
 * after a timer-interrupt and after each system call. Ordinary interrupts
 * don't handle signal-recognition, as that would clutter them up totally
 * unnecessarily.
 *
 * Stack layout in 'ret_from_system_call':
 *
 *	 0(%esp) - %eax
 *	 4(%esp) - %ebx
 *	 8(%esp) - %ecx
 *	 C(%esp) - %edx
 *	10(%esp) - %fs
 *	14(%esp) - %es
 *	18(%esp) - %ds
 *	1C(%esp) - %eip
 *	20(%esp) - %cs
 *	24(%esp) - %eflags
 *	28(%esp) - %oldesp
 *	2C(%esp) - %oldss
 */

SIG_CHLD	= 17
EAX		= 0x00
EBX		= 0x04
ECX		= 0x08
EDX		= 0x0C
FS		= 0x10
ES		= 0x14
DS		= 0x18
EIP		= 0x1C
CS		= 0x20
EFLAGS		= 0x24
OLDESP		= 0x28
OLDSS		= 0x2C

state	= 0		# these are offsets into the task-struct.
counter	= 4
priority = 8
signal	= 12
restorer = 16		# address of info-restorer
sig_fn	= 20		# table of 32 signal addresses

nr_system_calls = 67

.globl system_call,sys_fork,timer_interrupt
\end{lstlisting}
\section{system\_call函数}
检查输入的eax值，并根据eax值调用sys\_call\_table 对应的处理函数。
\begin{lstlisting}[breaklines]
.align 4 
bad_sys_call:
	movl $-1,%eax
	iret
.align 4
reschedule:
	pushl $ret_from_sys_call
	jmp schedule
.align 4
system_call:
	cmpl $nr_system_calls-1,%eax
	ja bad_sys_call
	push %ds
	push %es
	push %fs
	pushl %edx
	pushl %ecx		# push %ebx,%ecx,%edx as parameters
	pushl %ebx		# to the system call
	movl $0x10,%edx		# set up ds,es to kernel space
	mov %dx,%ds
	mov %dx,%es
	movl $0x17,%edx		# fs points to local data space
	mov %dx,%fs
	call sys_call_table(,%eax,4)
	pushl %eax
	movl current,%eax
	cmpl $0,state(%eax)		# state
	jne reschedule
	cmpl $0,counter(%eax)		# counter
	je reschedule
ret_from_sys_call:
	movl current,%eax		# task[0] cannot have signals
	cmpl task,%eax
	je 3f
	movl CS(%esp),%ebx		# was old code segment supervisor
	testl $3,%ebx			# mode? If so - don't check signals
	je 3f
	cmpw $0x17,OLDSS(%esp)		# was stack segment = 0x17 ?
	jne 3f
2:	movl signal(%eax),%ebx		# signals (bitmap, 32 signals)
	bsfl %ebx,%ecx			# %ecx is signal nr, return if none
	je 3f
	btrl %ecx,%ebx			# clear it
	movl %ebx,signal(%eax)
	movl sig_fn(%eax,%ecx,4),%ebx	# %ebx is signal handler address
	cmpl $1,%ebx
	jb default_signal		# 0 is default signal handler - exit
	je 2b				# 1 is ignore - find next signal
	movl $0,sig_fn(%eax,%ecx,4)	# reset signal handler address
	incl %ecx
	xchgl %ebx,EIP(%esp)		# put new return address on stack
	subl $28,OLDESP(%esp)
	movl OLDESP(%esp),%edx		# push old return address on stack
	pushl %eax			# but first check that it's ok.
	pushl %ecx
	pushl $28
	pushl %edx
	call verify_area
	popl %edx
	addl $4,%esp
	popl %ecx
	popl %eax
	movl restorer(%eax),%eax
	movl %eax,%fs:(%edx)		# flag/reg restorer
	movl %ecx,%fs:4(%edx)		# signal nr
	movl EAX(%esp),%eax
	movl %eax,%fs:8(%edx)		# old eax
	movl ECX(%esp),%eax
	movl %eax,%fs:12(%edx)		# old ecx
	movl EDX(%esp),%eax
	movl %eax,%fs:16(%edx)		# old edx
	movl EFLAGS(%esp),%eax
	movl %eax,%fs:20(%edx)		# old eflags
	movl %ebx,%fs:24(%edx)		# old return addr
3:	popl %eax
	popl %ebx
	popl %ecx
	popl %edx
	pop %fs
	pop %es
	pop %ds
	iret

default_signal:
	incl %ecx
	cmpl $SIG_CHLD,%ecx
	je 2b
	pushl %ecx
	call do_exit		# remember to set bit 7 when dumping core
	addl $4,%esp
	jmp 3b
\end{lstlisting}
\section{timer\_interrupt函数}
\begin{lstlisting}[breaklines]
.align 4
timer_interrupt:
	push %ds		# save ds,es and put kernel data space
	push %es		# into them. %fs is used by _system_call
	push %fs
	pushl %edx		# we save %eax,%ecx,%edx as gcc doesn't
	pushl %ecx		# save those across function calls. %ebx
	pushl %ebx		# is saved as we use that in ret_sys_call
	pushl %eax
	movl $0x10,%eax
	mov %ax,%ds
	mov %ax,%es
	movl $0x17,%eax
	mov %ax,%fs
	incl jiffies
	movb $0x20,%al		# EOI to interrupt controller #1
	outb %al,$0x20
	movl CS(%esp),%eax
	andl $3,%eax		# %eax is CPL (0 or 3, 0=supervisor)
	pushl %eax
	call do_timer		# 'do_timer(long CPL)' does everything from
	addl $4,%esp		# task switching to accounting ...
	jmp ret_from_sys_call
\end{lstlisting}
\section{sys\_fork函数}
\begin{lstlisting}[breaklines]
.align 4
sys_fork:
	call find_empty_process
	testl %eax,%eax
	js 1f
	push %gs
	pushl %esi
	pushl %edi
	pushl %ebp
	pushl %eax
	call copy_process
	addl $20,%esp
1:	ret
\end{lstlisting}

\chapter{硬件陷阱和异常处理源码kernel/traps.c}
\begin{lstlisting}[breaklines]
/*
 * 'Traps.c' handles hardware traps and faults after we have saved some
 * state in 'asm.s'. Currently mostly a debugging-aid, will be extended
 * to mainly kill the offending process (probably by giving it a signal,
 * but possibly by killing it outright if necessary).
 */
#include <string.h>

#include <linux/head.h>
#include <linux/sched.h>
#include <linux/kernel.h>
#include <asm/system.h>
#include <asm/segment.h>

#define get_seg_byte(seg,addr) ({ \
register char __res; \
__asm__("push %%fs;mov %%ax,%%fs;movb %%fs:%2,%%al;pop %%fs" \
	:"=a" (__res):"0" (seg),"m" (*(addr))); \
__res;})

#define get_seg_long(seg,addr) ({ \
register unsigned long __res; \
__asm__("push %%fs;mov %%ax,%%fs;movl %%fs:%2,%%eax;pop %%fs" \
	:"=a" (__res):"0" (seg),"m" (*(addr))); \
__res;})

#define _fs() ({ \
register unsigned short __res; \
__asm__("mov %%fs,%%ax":"=a" (__res):); \
__res;})

int do_exit(long code);

void page_exception(void);

void divide_error(void);
void debug(void);
void nmi(void);
void int3(void);
void overflow(void);
void bounds(void);
void invalid_op(void);
void device_not_available(void);
void double_fault(void);
void coprocessor_segment_overrun(void);
void invalid_TSS(void);
void segment_not_present(void);
void stack_segment(void);
void general_protection(void);
void page_fault(void);
void coprocessor_error(void);
void reserved(void);

static void die(char * str,long esp_ptr,long nr)
{
	long * esp = (long *) esp_ptr;
	int i;

	printk("%s: %04x\n\r",str,nr&0xffff);
	printk("EIP:\t%04x:%p\nEFLAGS:\t%p\nESP:\t%04x:%p\n",
		esp[1],esp[0],esp[2],esp[4],esp[3]);
	printk("fs: %04x\n",_fs());
	printk("base: %p, limit: %p\n",get_base(current->ldt[1]),get_limit(0x17));
	if (esp[4] == 0x17) {
		printk("Stack: ");
		for (i=0;i<4;i++)
			printk("%p ",get_seg_long(0x17,i+(long *)esp[3]));
		printk("\n");
	}
	str(i);
	printk("Pid: %d, process nr: %d\n\r",current->pid,0xffff & i);
	for(i=0;i<10;i++)
		printk("%02x ",0xff & get_seg_byte(esp[1],(i+(char *)esp[0])));
	printk("\n\r");
	do_exit(11);		/* play segment exception */
}

void do_double_fault(long esp, long error_code)
{
	die("double fault",esp,error_code);
}

void do_general_protection(long esp, long error_code)
{
	die("general protection",esp,error_code);
}

void do_divide_error(long esp, long error_code)
{
	die("divide error",esp,error_code);
}

void do_int3(long * esp, long error_code,
		long fs,long es,long ds,
		long ebp,long esi,long edi,
		long edx,long ecx,long ebx,long eax)
{
	int tr;

	__asm__("str %%ax":"=a" (tr):"0" (0));
	printk("eax\t\tebx\t\tecx\t\tedx\n\r%8x\t%8x\t%8x\t%8x\n\r",
		eax,ebx,ecx,edx);
	printk("esi\t\tedi\t\tebp\t\tesp\n\r%8x\t%8x\t%8x\t%8x\n\r",
		esi,edi,ebp,(long) esp);
	printk("\n\rds\tes\tfs\ttr\n\r%4x\t%4x\t%4x\t%4x\n\r",
		ds,es,fs,tr);
	printk("EIP: %8x   CS: %4x  EFLAGS: %8x\n\r",esp[0],esp[1],esp[2]);
}

void do_nmi(long esp, long error_code)
{
	die("nmi",esp,error_code);
}

void do_debug(long esp, long error_code)
{
	die("debug",esp,error_code);
}

void do_overflow(long esp, long error_code)
{
	die("overflow",esp,error_code);
}

void do_bounds(long esp, long error_code)
{
	die("bounds",esp,error_code);
}

void do_invalid_op(long esp, long error_code)
{
	die("invalid operand",esp,error_code);
}

void do_device_not_available(long esp, long error_code)
{
	die("device not available",esp,error_code);
}

void do_coprocessor_segment_overrun(long esp, long error_code)
{
	die("coprocessor segment overrun",esp,error_code);
}

void do_invalid_TSS(long esp,long error_code)
{
	die("invalid TSS",esp,error_code);
}

void do_segment_not_present(long esp,long error_code)
{
	die("segment not present",esp,error_code);
}

void do_stack_segment(long esp,long error_code)
{
	die("stack segment",esp,error_code);
}

void do_coprocessor_error(long esp, long error_code)
{
	die("coprocessor error",esp,error_code);
}

void do_reserved(long esp, long error_code)
{
	die("reserved (15,17-31) error",esp,error_code);
}
\end{lstlisting}
\section{trap\_init函数}
\begin{lstlisting}[breaklines]
void trap_init(void)
{
	int i;

	set_trap_gate(0,&divide_error);
	set_trap_gate(1,&debug);
	set_trap_gate(2,&nmi);
	set_system_gate(3,&int3);	/* int3-5 can be called from all */
	set_system_gate(4,&overflow);
	set_system_gate(5,&bounds);
	set_trap_gate(6,&invalid_op);
	set_trap_gate(7,&device_not_available);
	set_trap_gate(8,&double_fault);
	set_trap_gate(9,&coprocessor_segment_overrun);
	set_trap_gate(10,&invalid_TSS);
	set_trap_gate(11,&segment_not_present);
	set_trap_gate(12,&stack_segment);
	set_trap_gate(13,&general_protection);
	set_trap_gate(14,&page_fault);
	set_trap_gate(15,&reserved);
	set_trap_gate(16,&coprocessor_error);
	for (i=17;i<32;i++)
		set_trap_gate(i,&reserved);
/*	__asm__("movl $0x3ff000,%%eax\n\t"
		"movl %%eax,%%db0\n\t"
		"movl $0x000d0303,%%eax\n\t"
		"movl %%eax,%%db7"
		:::"ax");*/
}
\end{lstlisting}

\chapter{内存管理源码mm/memory.c}
\begin{lstlisting}[breaklines]
#include <signal.h>

#include <linux/config.h>
#include <linux/head.h>
#include <linux/kernel.h>
#include <asm/system.h>

int do_exit(long code);

#define invalidate() \
__asm__("movl %%eax,%%cr3"::"a" (0))

#if (BUFFER_END < 0x100000)
#define LOW_MEM 0x100000
#else
#define LOW_MEM BUFFER_END
#endif

/* these are not to be changed - thay are calculated from the above */
#define PAGING_MEMORY (HIGH_MEMORY - LOW_MEM)
#define PAGING_PAGES (PAGING_MEMORY/4096)
#define MAP_NR(addr) (((addr)-LOW_MEM)>>12)

#if (PAGING_PAGES < 10)
#error "Won't work"
#endif

#define copy_page(from,to) \
__asm__("cld ; rep ; movsl"::"S" (from),"D" (to),"c" (1024))

static unsigned short mem_map [ PAGING_PAGES ] = {0,};
\end{lstlisting}
\section{get\_free\_page函数}
mem\_map 数组记录了所有物理内存的分配和使用情况，我们首先要找到一页空闲的物理内存。
\begin{lstlisting}[breaklines]
/*
 * Get physical address of first (actually last :-) free page, and mark it
 * used. If no free pages left, return 0.
 */
unsigned long get_free_page(void)
{
register unsigned long __res asm("ax");

__asm__("std ; repne ; scasw\n\t"
	"jne 1f\n\t"
	"movw $1,2(%%edi)\n\t"
	"sall $12,%%ecx\n\t"
	"movl %%ecx,%%edx\n\t"
	"addl %2,%%edx\n\t"
	"movl $1024,%%ecx\n\t"
	"leal 4092(%%edx),%%edi\n\t"
	"rep ; stosl\n\t"
	"movl %%edx,%%eax\n"
	"1:"
	:"=a" (__res)
	:"0" (0),"i" (LOW_MEM),"c" (PAGING_PAGES),
	"D" (mem_map+PAGING_PAGES-1)
	);
return __res;
}

/*
 * Free a page of memory at physical address 'addr'. Used by
 * 'free_page_tables()'
 */
void free_page(unsigned long addr)
{
	if (addr<LOW_MEM) return;
	if (addr>HIGH_MEMORY)
		panic("trying to free nonexistent page");
	addr -= LOW_MEM;
	addr >>= 12;
	if (mem_map[addr]--) return;
	mem_map[addr]=0;
	panic("trying to free free page");
}

/*
 * This function frees a continuos block of page tables, as needed
 * by 'exit()'. As does copy_page_tables(), this handles only 4Mb blocks.
 */
int free_page_tables(unsigned long from,unsigned long size)
{
	unsigned long *pg_table;
	unsigned long * dir, nr;

	if (from & 0x3fffff)
		panic("free_page_tables called with wrong alignment");
	if (!from)
		panic("Trying to free up swapper memory space");
	size = (size + 0x3fffff) >> 22;
	dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */
	for ( ; size-->0 ; dir++) {
		if (!(1 & *dir))
			continue;
		pg_table = (unsigned long *) (0xfffff000 & *dir);
		for (nr=0 ; nr<1024 ; nr++) {
			if (1 & *pg_table)
				free_page(0xfffff000 & *pg_table);
			*pg_table = 0;
			pg_table++;
		}
		free_page(0xfffff000 & *dir);
		*dir = 0;
	}
	invalidate();
	return 0;
}
\end{lstlisting}
\section{copy\_page\_tables函数}
在head.s中，我们为page\_dir 预留了4k内存，可以容纳1024个page\_table ，但当时我们只预留了两个page\_table 用于内核寻址8M内存空间。现在，当我们需要首先要找到空闲的物理内存块作为to\_page\_table ，并将这个新的page\_table 登记到dir中的to\_dir 位置， 然后将from\_page\_table 的page复制到to\_page\_table中， 这样，to\_page\_table 和 from\_page\_table 的page实际映射到了相同的物理页面。我们实际没有复制任何page指向的物理内存块。
\begin{lstlisting}[breaklines]
/*
 *  Well, here is one of the most complicated functions in mm. It
 * copies a range of linerar addresses by copying only the pages.
 * Let's hope this is bug-free, 'cause this one I don't want to debug :-)
 *
 * Note! We don't copy just any chunks of memory - addresses have to
 * be divisible by 4Mb (one page-directory entry), as this makes the
 * function easier. It's used only by fork anyway.
 *
 * NOTE 2!! When from==0 we are copying kernel space for the first
 * fork(). Then we DONT want to copy a full page-directory entry, as
 * that would lead to some serious memory waste - we just copy the
 * first 160 pages - 640kB. Even that is more than we need, but it
 * doesn't take any more memory - we don't copy-on-write in the low
 * 1 Mb-range, so the pages can be shared with the kernel. Thus the
 * special case for nr=xxxx.
 */
int copy_page_tables(unsigned long from,unsigned long to,long size)
{
	unsigned long * from_page_table;
	unsigned long * to_page_table;
	unsigned long this_page;
	unsigned long * from_dir, * to_dir;
	unsigned long nr;

	if ((from&0x3fffff) || (to&0x3fffff))
		panic("copy_page_tables called with wrong alignment");
	from_dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */
	to_dir = (unsigned long *) ((to>>20) & 0xffc);
	size = ((unsigned) (size+0x3fffff)) >> 22;
	for( ; size-->0 ; from_dir++,to_dir++) {
		if (1 & *to_dir)
			panic("copy_page_tables: already exist");
		if (!(1 & *from_dir))
			continue;
		from_page_table = (unsigned long *) (0xfffff000 & *from_dir);
		if (!(to_page_table = (unsigned long *) get_free_page()))
			return -1;	/* Out of memory, see freeing */
		*to_dir = ((unsigned long) to_page_table) | 7;
		nr = (from==0)?0xA0:1024;
		for ( ; nr-- > 0 ; from_page_table++,to_page_table++) {
			this_page = *from_page_table;
			if (!(1 & this_page))
				continue;
			this_page &= ~2;
			*to_page_table = this_page;
			if (this_page > LOW_MEM) {
				*from_page_table = this_page;
				this_page -= LOW_MEM;
				this_page >>= 12;
				mem_map[this_page]++;
			}
		}
	}
	invalidate();
	return 0;
}

/*
 * This function puts a page in memory at the wanted address.
 * It returns the physical address of the page gotten, 0 if
 * out of memory (either when trying to access page-table or
 * page.)
 */
unsigned long put_page(unsigned long page,unsigned long address)
{
	unsigned long tmp, *page_table;

/* NOTE !!! This uses the fact that _pg_dir=0 */

	if (page < LOW_MEM || page > HIGH_MEMORY)
		printk("Trying to put page %p at %p\n",page,address);
	if (mem_map[(page-LOW_MEM)>>12] != 1)
		printk("mem_map disagrees with %p at %p\n",page,address);
	page_table = (unsigned long *) ((address>>20) & 0xffc);
	if ((*page_table)&1)
		page_table = (unsigned long *) (0xfffff000 & *page_table);
	else {
		if (!(tmp=get_free_page()))
			return 0;
		*page_table = tmp|7;
		page_table = (unsigned long *) tmp;
	}
	page_table[(address>>12) & 0x3ff] = page | 7;
	return page;
}

void un_wp_page(unsigned long * table_entry)
{
	unsigned long old_page,new_page;

	old_page = 0xfffff000 & *table_entry;
	if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {
		*table_entry |= 2;
		return;
	}
	if (!(new_page=get_free_page()))
		do_exit(SIGSEGV);
	if (old_page >= LOW_MEM)
		mem_map[MAP_NR(old_page)]--;
	*table_entry = new_page | 7;
	copy_page(old_page,new_page);
}	

/*
 * This routine handles present pages, when users try to write
 * to a shared page. It is done by copying the page to a new address
 * and decrementing the shared-page counter for the old page.
 */
void do_wp_page(unsigned long error_code,unsigned long address)
{
	un_wp_page((unsigned long *)
		(((address>>10) & 0xffc) + (0xfffff000 &
		*((unsigned long *) ((address>>20) &0xffc)))));

}

void write_verify(unsigned long address)
{
	unsigned long page;

	if (!( (page = *((unsigned long *) ((address>>20) & 0xffc)) )&1))
		return;
	page &= 0xfffff000;
	page += ((address>>10) & 0xffc);
	if ((3 & *(unsigned long *) page) == 1)  /* non-writeable, present */
		un_wp_page((unsigned long *) page);
	return;
}

void do_no_page(unsigned long error_code,unsigned long address)
{
	unsigned long tmp;

	if ((tmp=get_free_page()))
		if (put_page(tmp,address))
			return;
	do_exit(SIGSEGV);
}

void calc_mem(void)
{
	int i,j,k,free=0;
	long * pg_tbl;

	for(i=0 ; i<PAGING_PAGES ; i++)
		if (!mem_map[i]) free++;
	printk("%d pages free (of %d)\n\r",free,PAGING_PAGES);
	for(i=2 ; i<1024 ; i++) {
		if (1&pg_dir[i]) {
			pg_tbl=(long *) (0xfffff000 & pg_dir[i]);
			for(j=k=0 ; j<1024 ; j++)
				if (pg_tbl[j]&1)
					k++;
			printk("Pg-dir[%d] uses %d pages\n",i,k);
		}
	}
}
\end{lstlisting}
\chapter{页内存访问异常处理源码mm/page.s}
页异常中断处理程序。当出现页内存访问异常时，错误码由CPU自动产生并压栈，出错时的线性地址保则存在控制寄存器CR2中。copy on write等技术会利用页访问异常，以减少不必要的内存复制，出现页异常反而是正常现象。
\section{page\_fault函数}
\begin{lstlisting}[breaklines]
/*
 * page.s contains the low-level page-exception code.
 * the real work is done in mm.c
 */

.globl page_fault

page_fault:
	xchgl %eax,(%esp)	# `从堆栈中获取错误码`
	pushl %ecx
	pushl %edx
	push %ds
	push %es
	push %fs
	movl $0x10,%edx
	mov %dx,%ds
	mov %dx,%es
	mov %dx,%fs
	movl %cr2,%edx
	pushl %edx
	pushl %eax
	testl $1,%eax	# `测试错误码中的页存在标志bit0`
	jne 1f
	call do_no_page	# `页不存在，调用缺页处理`
	jmp 2f
1:	call do_wp_page	# `页存在，调用写保护处理`
2:	addl $8,%esp
	pop %fs
	pop %es
	pop %ds
	popl %edx
	popl %ecx
	popl %eax
	iret
\end{lstlisting}
\chapter{lib}
\section{ctype.c}
\begin{lstlisting}[breaklines]
\end{lstlisting}
\section{errno.c}
\section{\_exit.c}
\chapter{头文件include}
内核使用到的所有头文件都保存在include目录下，其中，和计算机体系结构密切相关的部分放在asm子目录下，和linux特有定义相关的放在linux子目录下，和内核资源相关的放在sys子目录下。
\section{include目录下的文件}
\section{ctype.h}
\section{errno.h}
\section{signal.h}
\section{time.h}
\section{unistd.h}
\section{include/asm目录下的文件}
\section{memory.h}
\section{include/linux目录下的文件}
\section{config.h}
\section{fs.h}
\section{head.h}
\section{kernel.h}
\section{mm.h}
\section{sched.h}
\section{sys.h}
\section{include/sys目录下的文件}
\section{stat.h}
\section{times.h}
\section{utsname.h}
\section{wait.h}
\chapter{工程文件}
\section{Makefile}
相对0.002, 增加了mm目录，Makefile需要增加到mm目录下的Makefile的调用；
\begin{lstlisting} [breaklines]
AS86    =as86 -0 -a
LD86    =ld86 -0

AS      =as --32
LD      =ld -melf_i386 -e startup_32 -Ttext 0
LDFLAGS =-s -x -M
CC      =gcc -m32
CFLAGS  =-Wall -O -fstrength-reduce -fomit-frame-pointer
CPP     =gcc -E -nostdinc -Iinclude

ARCHIVES=kernel/kernel.o mm/mm.o
#fs/fs.o
#LIBS   =lib/lib.a

.c.s:
        $(CC) $(CFLAGS) \
        -nostdinc -Iinclude -S -o $*.s $<
.s.o:
        $(AS) -c -o $*.o $<
.c.o:
        $(CC) $(CFLAGS) \
        -nostdinc -Iinclude -c -o $*.o $<

all:    Image

Image: boot/boot tools/system tools/build
        tools/build boot/boot tools/system > Image
        sync

tools/build: tools/build.c
        $(CC) $(CFLAGS) \
        -o tools/build tools/build.c

boot/head.o: boot/head.s

tools/system:   boot/head.o init/main.o \
                $(ARCHIVES) $(LIBS)
        $(LD) $(LDFLAGS) boot/head.o init/main.o \
                $(ARCHIVES) \
        -o tools/system > System.map

kernel/kernel.o:
        (cd kernel; make)

mm/mm.o:
       (cd mm; make)

#fs/fs.o:
#       (cd fs; make)

#lib/lib.a:
#       (cd lib; make)

boot/boot:      boot/boot.s tools/system
        (./tmp.sh)
        $(AS86) -o boot/boot.o tmp.s
        rm -f tmp.s
        $(LD86) -s -o boot/boot boot/boot.o

clean:
        rm -f Image System.map tmp_make boot/boot core
        rm -f init/*.o boot/*.o tools/system tools/build
        (cd mm;make clean)
#       (cd fs;make clean)
        (cd kernel;make clean)
#       (cd lib;make clean)

backup: clean
        (cd .. ; tar cf - linux | compress16 - > backup.Z)
        sync

dep:
        sed '/\#\#\# Dependencies/q' < Makefile > tmp_make
        (for i in init/*.c;do echo -n "init/";$(CPP) -M $$i;done) >> tmp_make
        cp tmp_make Makefile
#       (cd fs; make dep)
        (cd kernel; make dep)
        (cd mm; make dep)

### Dependencies:
init/main.o: init/main.c include/linux/tty.h include/termios.h
\end{lstlisting}
\section{kernel/Makefile}
\paragraph{1}kernel目录下的Makefile和主Makefile类似，主要的变化是增加文件。
\begin{lstlisting}

# Makefile for the FREAX-kernel.
#
# Note! Dependencies are done automagically by 'make dep', which also
# removes any old dependencies. DON'T put your own dependencies here
# unless it's something special (ie not a .c file).
#

AR      =gar
AS      =as --32
LD      =ld -melf_i386
LDFLAGS =-s -x
CC      =gcc -m32
CFLAGS  =-w -O -fstrength-reduce -fomit-frame-pointer \
        -finline-functions -nostdinc -I../include -fno-stack-protector
CPP     =gcc -E -nostdinc -I../include

.c.s:
        $(CC) $(CFLAGS) \
        -S -o $*.s $<
.s.o:
        $(AS) -c -o $*.o $<
.c.o:
        $(CC) $(CFLAGS) \
        -c -o $*.o $<

OBJS  = sched.o console.o tty_io.o printk.o vsprintf.o \
        system_call.o traps.o asm.o fork.o \
        panic.o mktime.o exit.o\
#        keyboard.o rs_io.o hd.o sys.o serial.o

kernel.o: $(OBJS)
        $(LD) -r -o kernel.o $(OBJS)
        sync

clean:
        rm -f core *.o *.a tmp_make
        for i in *.c;do rm -f ``basename $$i .c``.s;done      

dep:
        sed '/\#\#\# Dependencies/q' < Makefile > tmp_make
        (for i in *.c;do echo -n ``echo $$i | sed 's,\.c,\.s,'``" "; \
                $(CPP) -M $$i;done) >> tmp_make
        cp tmp_make Makefile
### Dependencies:
console.s console.o: console.c ../include/asm/io.h ../include/asm/system.h \
 ../include/linux/tty.h ../include/termios.h
printk.s printk.o: printk.c ../include/stdarg.h ../include/stddef.h
sched.s sched.o: sched.c
tty_io.s tty_io.o: tty_io.c ../include/linux/tty.h ../include/termios.h
clean:
        rm -f core *.o *.a tmp_make
        for i in *.c;do rm -f ``basename $$i .c``.s;done
\end{lstlisting}
\section{mm/Makefile}
\paragraph{1}mm目录下的Makefile和主Makefile类似；
\begin{lstlisting}
CC	=gcc -m32
CFLAGS	=-O -Wall -fstrength-reduce -fomit-frame-pointer \
	-finline-functions -nostdinc -I../include
AS	=as --32
AR	=ar
LD	=ld -melf_i386
CPP	=gcc -E -nostdinc -I../include

.c.o:
	$(CC) $(CFLAGS) \
	-c -o $*.o $<
.s.o:
	$(AS) -o $*.o $<
.c.s:
	$(CC) $(CFLAGS) \
	-S -o $*.s $<

OBJS	= memory.o page.o

all: mm.o

mm.o: $(OBJS)
	$(LD) -r -o mm.o $(OBJS)

clean:
	rm -f core *.o *.a tmp_make
	for i in *.c;do rm -f ``basename $$i .c``.s;done

dep:
	sed '/\#\#\# Dependencies/q' < Makefile > tmp_make
	(for i in *.c;do $(CPP) -M $$i;done) >> tmp_make
	cp tmp_make Makefile

### Dependencies:
memory.o: memory.c ../include/signal.h ../include/sys/types.h \
 ../include/linux/config.h ../include/linux/head.h \
 ../include/linux/kernel.h ../include/asm/system.h
\end{lstlisting}
\section{lib/Makefile}

\end{CJK}
\end{document}
